package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         140,
		Discription: "从字典中选单词（可重复）组成指定字符串，返回所有结果",
		Level:       3,
		Labels: map[string]int{
			"哈希表":  1,
			"动态规划": 1,
			"递归":   1,
		},
	})
}

func WordBreak2(s string, wordDict []string) []string {
	n := len(s)
	wordMap := make(map[string]bool, 0)
	for _, word := range wordDict {
		wordMap[word] = true
	}

	//先得出s每一个位置是否能被构成
	dp := make([]bool, n+1)
	dp[0] = true
	for j := 1; j <= n; j++ {
		for i := j - 1; i >= 0; i-- {
			if wordMap[s[i:j]] {
				dp[j] = dp[i]
				if dp[j] {
					break
				}
			}
		}
	}

	res := make([]string, 0)
	str := ""
	//字符串从右向左递归，对应dp[:end]
	var travel func(int)
	travel = func(end int) {
		if end == 0 {
			res = append(res, str[1:])
			return
		}

		for i := end - 1; i >= 0; i-- {
			if wordMap[s[i:end]] && dp[i] {
				str = " " + s[i:end] + str
				travel(i)
				str = str[end-i+1:]
			}
		}
	}

	travel(n)
	return res
}
